Graphical and/or textual models are used in a multitude of areas of engineering and design to design, test and verify systems applicable to almost all fields of human endeavor, from biological systems, to mechanical and/or electrical systems, to finance and statistics applications. Model-based design typically involves representing a real-world system using a model, which model may then be tested, improved, and/or used to implement the actual system.
Logic or structure of a model or of any generic software and/or hardware program or module may be represented as a control flow graph (CFG). A CFG is a directed graph, in which nodes represent computational statements, elements or expressions, and edges represent transfer of control between nodes. A control flow typically includes all possible execution paths, and each possible execution path of the module has a corresponding path from the entry to the exit node of the graph.
Control flow graphs may be represented graphically and/or textually, or as in-memory representations. There are numerous uses for control flow graphs: code optimization, compilation and interpretation, code visualization, static analysis, dynamic testing, etc. In general, a control flow graph is one of many possible representations of a software and/or hardware module. The CFG may be an intermediate representation, derived from the original representation, or the software or graphical code itself may represent a control flow graph.
A typical control flow graph may have a single entry node and a single exit node, with one or more paths in between, indicating possible flow of execution. Control flow graphs may be viewed as hierarchical—that is, a block in a single entry single exit (SESE) CFG may sometimes be represented as a SESE control flow graph. Conversely, a single entry single exit region of a CFG may be abstracted into one or more blocks in a larger CFG. Such hierarchical change of levels of representation is often used in compilation, optimization, static analysis, and other applications, where it may be useful to analyze a portion of the module at different levels of detail. In some cases, a compiler, optimizer or analyzer may make several paths through a CFG, creating blocks of out sub-graphs or subdividing blocks into SESE sub-graphs.
Control flow graphs may contain cycles, also referred to as “loops,”—that is, sections where one or more exits from a block lead to a path in a graph already traveled on the way to that block. Elements within and outside of the cycles may be subdivided into various SESE sub-graphs, and the cycles themselves may be restructured during compilation or optimization, although most frequently a cycle cannot be optimized out to non-cyclical structures altogether.
Control flow graphs may be expressed in a number of ways: graphically, textually or in a combination thereof. CFGs may be a final result of compilation or code generation, or they may be used for code generation. It is usual for an intermediate representation, used in code generation, compilation, execution or analysis, to be a representation of a control flow graph. Moreover, some assembly or hardware representations specifically represent a control flow graph. For example, a section of assembly-level code may be thought as a CFG.